/*
Date:20210420 19:35pm
key：代码改编自华为4.14笔试题，那题要求最小跳跃次数，这题问能不能跳得到。那就检查每次i有没有变动，能到就每次都会变化。
*/
class Solution {
public:
    void jump(vector<int>& nums, int* B,int &i, int& n)
{
	//遍历i及的右边A[i]个
	int new_i=i;
	int j;
	int max_len = 0;
	for (j = i; j <= i + nums[i]&&j<nums.size(); j++)
	{
		//cout << j << " ";
		if (B[j] >= max_len)
		{
            if(B[j]>=nums.size()-1){i = nums.size()-1;return;}
			new_i = j;
			max_len = B[j];
			//if (j + A[j]+1 >= n)
			//{
			//	i = n;
			//	return;
			//}
		}
	}
	i = new_i;
}
    bool canJump(vector<int>& nums) {
        	int i, j, n;
    n=nums.size();
	if (n == 0) { return 0; }
    if (n == 1) { return 1; }
    if (n == 2) { if(nums[0]!=0)return 1;else{return 0;}}
    //if (n <3&&nums[0]>0) { return 1; }
	//每个点能到的最远
	int* B = new int[n];
	for (i = 0; i < n; i++)
	{
		B[i] = i + nums[i];
	}
	i = 0;
	int count = 0;
    int p;
	while (1)
	{
        //每次检查i有没有变化，没变化就是跳不出去了
        p=i;
		//每次把下标起点放入
		jump(nums,B, i,n);
        if(p==i){return 0;}
		//cout << i << " ";
		count++;
		//因为i是下标所以要+1
		if (i+1 >= n)
		{
			return 1;
		}
		
	}
	return 0;
    }
};